package com.hao.link;

import java.util.ArrayList;
import java.util.List;

/**
 * TODO
 *
 * @author 97472
 * @version 1.0
 * @date 2021/4/21 10:41
 */
public class MyJosephu {

    private Node firstNode;

    private Integer size = 0;


    public void add(Integer num) {
        Node newNode = new Node(num, null);
        boolean hasFirstNode = firstNode !=null;
        if (hasFirstNode){
            Node lastNode = getLastNode();
            lastNode.nextNode = newNode;
            newNode.nextNode = firstNode;
        }else {
            firstNode = newNode;
            firstNode.nextNode = firstNode;
        }
        size++;
    }

    private Node getLastNode(){
        if (firstNode == null){
            return null;
        }
        Node lastNode = firstNode;
        boolean hastNext = true;
        while (hastNext){
            lastNode = lastNode.nextNode;
            hastNext = lastNode.nextNode != firstNode;
        }
        return lastNode;
    }

    public List<Integer> solverJosephu(Integer n, Integer startIndex, Integer time){
        // 数据校验
        if (n < 0||startIndex < 0 || startIndex > n){
            throw new RuntimeException("输入的数据有异常");
        }

        // 记录出队编号的集合
        List<Integer> numArr = new ArrayList();
        // 初始化队列
        for (int i = 1; i <= n; i++) {
            add(i);
        }

        // 将first指向startIndex报数
        for (int i = 0; i < startIndex-1; i++) {
            firstNode = firstNode.nextNode;
        }

        // 进行出队
        boolean isOver = false;
        while (!isOver){
            // 出队的节点
            Node out = null;
            // 获取出队节点的前一个节点
            Node before = firstNode;
            for (int i = 0; i < time -2; i++) {
               before = before.nextNode;
            }
            // 将该节点抽离队列
            if (size != 1){
                out = before.nextNode;
                before.nextNode = out.nextNode;
                firstNode = out.nextNode;
                size--;
            }else {
                out = firstNode;
                isOver = true;
            }
            numArr.add(out.num);
        }
        return numArr;
    }

    class Node{
        /**
         * //TODO 用户要存放的数据
         **/
        private Integer num;
        /**
         * //TODO 下一个节点的地址
         **/
        private Node nextNode;

        public Node(Integer num, Node nextNode) {
            this.num = num;
            this.nextNode = nextNode;
        }
    }
}
